'''
Created on May 22, 2009

@author: Roni
'''
from cliques.cliqueAlgorithm import cliqueAlgorithm
from cliques.kPotentialClique import kPotentialClique

class potentialBasedSearch(cliqueAlgorithm):
    '''
    classdocs
    '''

    def __init__(self):
        '''
        Constructor
        '''
        self.remove_cliques=set()
        self.add_cliques=set()
        self.fullPotential = None 
        # If not None then fullPotential is a potential k-clique of with k-1 nodes => 
        # (a k-clique has been found)

        cliqueAlgorithm.__init__(self)
       

    def generate(self, parent, new_node):
        if self.generated_to_kPc.has_key(new_node)==False:
            self.generated_to_kPc[new_node]=[]
        return cliqueAlgorithm.generate(self, parent, new_node)



    def setup(self, unknown_graph, k, start_node):
        # statistics
        self.pcdb_size = []
        self.max_gcn = []
        self.generated_size=[]
        self.fullPotential = None
        
        self.pcdb=set()
        self.node_to_kPc = dict()
        self.generated_to_kPc = dict()
        for node in unknown_graph.nodes():
            self.node_to_kPc[node]=list()
            self.generated_to_kPc[node]=list()
        cliqueAlgorithm.setup(self, unknown_graph, k, start_node)        
    
    
    

    def expand(self, node):
        cliqueAlgorithm.expand(self,node)
        
        generated_neighbors = filter(lambda x:x in self.generated,self.unknown_graph.neighbors(node))
        self.remove_cliques.clear()
        self.add_cliques.clear()
        for kPc in self.generated_to_kPc[node]:
            # Remove from gcn and prune kPc if necessary
            kPc.gcn.remove(node)
            if kPc.is_potential(self.k)==False:
                self.remove_cliques.add(kPc)
                
            # Extend if relevant
            potential_gcn=filter(lambda x:x in generated_neighbors,kPc.gcn)
            extended_kPc = kPotentialClique(kPc.core+[node],potential_gcn)
            if extended_kPc.is_potential(self.k):
                self.add_cliques.add(extended_kPc)
        
        # Possible to prune irrelevant nodes by degree (but not generated)
        if len(generated_neighbors)>=self.k-1:
            core = [node]
            self.add_cliques.add(kPotentialClique(core,generated_neighbors))

        # Update PCDB with new/redundant potential cliques
        self.pcdb.update(self.add_cliques)
        for new_clique in self.add_cliques:
            #print "added %s " % new_clique.core
            for core_member in new_clique.core:
                if self.node_to_kPc.has_key(core_member)==False:
                    self.node_to_kPc[core_member]=[]
                self.node_to_kPc[core_member].append(new_clique)
            for gcn_member in new_clique.gcn:
                if self.generated_to_kPc.has_key(gcn_member)==False:
                    self.generated_to_kPc[gcn_member]=[]
                self.generated_to_kPc[gcn_member].append(new_clique)
            
            if len(new_clique.core)>=self.k-1:
                for gcn_member in new_clique.gcn:
                    self.notify_clique_found(new_clique.core+[gcn_member])
            
        self.pcdb.difference_update(self.remove_cliques)
        for removed_clique in self.remove_cliques:
            #print "removed %s " % removed_clique.core
            for core_member in removed_clique.core:
                self.node_to_kPc[core_member].remove(removed_clique)
            for gcn_member in removed_clique.gcn:
                self.generated_to_kPc[gcn_member].remove(removed_clique)
                
        del self.generated_to_kPc[node][:]

    def notify_clique_found(self,a_clique):
        ''' An event that is raised when a new k-clique has been found '''
        self.fullPotential = a_clique

    def average(self,values):
        return sum(values, 0.0) / len(values)

    def stdev(self,values,average):
        var_sum=0
        for value in values:
            var_sum= var_sum+abs(values-average)
        return var_sum/len(values)
     
         
    def clique_found(self):
        if self.fullPotential is not None:
            self.done=True
            return True
        return False     

     
    def __str__(self):
        return "potentialBasedSearch"
    
